import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 面试题38：字符串的排列
 */
public class Offer_38 {
    List<String> ans = new ArrayList<>();
    char[] charArray;

    /**
     * Krahets 的题解
     */
    public String[] permutation(String s) {
        charArray = s.toCharArray();
        // 从第一层开始递归
        dfs(0);
        return ans.toArray(new String[ans.size()]);
    }

    public void dfs(int x) {
        if (x == charArray.length - 1) {
            // 添加排列方案
            ans.add(new String(charArray));
            return;
        }
        // 防止同一层递归出现重复元素
        Set<Character> set = new HashSet<>();
        for (int i = x; i < charArray.length; i++) {
            // 重复，因此剪枝
            if (set.contains(charArray[i])) {
                continue;
            }
            set.add(charArray[i]);
            // 交换，将 c[i] 固定在第 x 位
            swap(i, x);
            // 开启固定第 x + 1 位字符
            dfs(x + 1);
            // 恢复交换
            swap(i, x);
        }
    }

    public void swap(int i, int j) {
        char temp = charArray[i];
        charArray[i] = charArray[j];
        charArray[j] = temp;
    }
}
